编译原理

# 编译原理

[TOC]

# 一、什么是编译

将编程语言翻译成机器语言

任何js代码片段在执行前都要进行编译，不过可以通过重编译和迟编译来保证性能最佳。

# 二、编译三步走

# 2.1 分词/词法分析（Tokenizing/Lexing）

将字符串分解成词法单元

var a = 1; 分解成 var, a, =, 1, ;

空格是否作为词法单元，取决于它本身是否有意义。

# 2.2 解析/语法分析（Parsing）

词法单元流（数组）转换成抽象语法树（Abstract Syntax Tree, AST）

AST：VariableDeclaration（顶级节点）

Identifier（子节点）值为a

AssignmentExpression（子节点）包含 NumericLiteral （子节点）值为2

# 2.3 代码生成

AST转换成可执行的代码

最后转化为一组机器指令，用来分配内存，创建一个叫作a的变量，并将一个值存储在a中。

# 解析代码

# 3.1 词（token）是如何被拆分的

<p class="a">text text text</p>

最小有意义单元的定义来拆分，第一个词（token）是什么呢？显然，作为一个词（token），整个 p 标签肯定是过大了（它甚至可以嵌套）。

那么，只用 p 标签的开头是不是合适吗？我们考虑到起始标签也是会包含属性的，最小的意义单元其实是“<p” ，所以“ <p” 就是我们的第一个词（token）。

我们继续拆分，可以把这段代码依次拆成词（token）：

<p“标签开始”的开始；
class=“a” 属性；
> “标签开始”的结束；
text text text 文本；
标签结束。

这些词（token）长的样子：

根据这样的分析，现在我们讲讲浏览器是如何用代码实现，我们设想，代码开始从 HTTP 协议收到的字符流读取字符。

在接受第一个字符之前，我们完全无法判断这是哪一个词（token），不过，随着我们接受的字符越来越多，拼出其他的内容可能性就越来越少。

比如，假设我们接受了一个字符“ < ” 我们一下子就知道这不是一个文本节点啦。

之后我们再读一个字符，比如就是 x，那么我们一下子就知道这不是注释和 CDATA 了，接下来我们就一直读，直到遇到“>”或者空格，这样就得到了一个完整的词（token）了。

实际上，我们每读入一个字符，其实都要做一次决策，而且这些决定是跟“当前状态”有关的。在这样的条件下，浏览器工程师要想实现把字符流解析成词（token），最常见的方案就是使用状态机。

# 3.2 状态机

绝大多数语言的词法部分都是用状态机实现的。那么我们来把部分词（token）的解析画成一个状态机看看：

状态机

状态机的初始状态，我们仅仅区分 “< ”和 “非 <”：

如果获得的是一个非 < 字符，那么可以认为进入了一个文本节点；
如果获得的是一个 < 字符，那么进入一个标签状态。

不过当我们在标签状态时，则会面临着一些可能性。

比如下一个字符是“ ! ” ，那么很可能是进入了注释节点或者 CDATA 节点。
如果下一个字符是 “/ ”，那么可以确定进入了一个结束标签。
如果下一个字符是字母，那么可以确定进入了一个开始标签。
如果我们要完整处理各种 HTML 标准中定义的东西，那么还要考虑“ ? ”“% ”等内容。

用状态机做词法分析，其实正是把每个词的“特征字符”逐个拆开成独立状态，然后再把所有词的特征字符链合并起来，形成一个联通图结构。

由于状态机设计属于编译原理的基本知识，这里仅作一个简要的介绍。

# 3.2.1 JS实现状态机

状态机是一种没有办法封装的东西，所以我们永远不要试图封装状态机。
把每个函数当做一个状态，参数是接受的字符，返回值是下一个状态函数。

var data = function(c){
    if(c=="&") {
        return characterReferenceInData;
    }
    if(c=="<") {
        return tagOpen;
    }
    else if(c=="\0") {
        error();
        emitToken(c);
        return data;
    }
    else if(c==EOF) {
        emitToken(EOF);
        return data;
    }
    else {
        emitToken(c);
        return data;
    }
};
var tagOpenState = function tagOpenState(c){
    if(c=="/") {
        return endTagOpenState;
    }
    if(c.match(/[A-Z]/)) {
        token = new StartTagToken();
        token.name = c.toLowerCase();
        return tagNameState;
    }
    if(c.match(/[a-z]/)) {
        token = new StartTagToken();
        token.name = c;
        return tagNameState;
    }
    if(c=="?") {
        return bogusCommentState;
    }
    else {
        error();
        return dataState;
    }
};
//……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

这里的状态机，每一个状态是一个函数，通过“if else”来区分下一个字符做状态迁移。这里所谓的状态迁移，就是当前状态函数返回下一个状态函数。

这样，我们的状态迁移代码非常的简单：

var state = data;
var char
while(char = getInput())
    state = state(char);

1
2
3
4

这段代码的关键一句是“ state = state(char) ”，不论我们用何种方式来读取字符串流，我们都可以通过 state 来处理输入的字符流，这里用循环是一个示例，真实场景中，可能是来自 TCP 的输出流。

状态函数通过代码中的 emitToken 函数来输出解析好的 token（词），我们只需要覆盖 emitToken，即可指定对解析结果的处理方式。

词法分析器接受字符的方式很简单，就像下面这样：

function HTMLLexicalParser(){
 
    // 状态函数们……
    function data() {
        // ……
    }
 
    function tagOpen() {
        // ……
    }
    // ……
    var state = data;
    this.receiveInput = function(char) {
        state = state(char);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

至此，就把字符流拆成了词（token）了。

Class 组件开发

LinHuijuan's Blog

Choose mode